Công việc thiết kế chiếc tàu ngầm hạt nhân đầu tiên của Hải quân Mỹ đã được bắt đầu vào tháng 3/1950 trong dự án SCB 64.[6][7] Vào tháng 7/1951, Quốc hội Mỹ bật đèn xanh cho việc chế tạo tàu ngầm hạt nhân cho Hải quân Mỹ, kế hoạch phát triển được giao cho Thuyền trưởng (về sau là Đô đốc) Hyman G. Rickover, USN, người được coi là Cha đẻ của "hạm đội tàu hạt nhân Hải quân Mỹ"[8] 12/12/1951, US Department of the Navy thông báo đặt tên cho tàu ngầm là Nautilus, khiến nó trở thành chiếc tàu ngầm thứ 4 của Hải quân Mỹ được đặt tên là Nautilus. Chiếc tàu sẽ mang số hiệu khung SSN-571.[9] Nó được thừa hưởng thành tựu trong chương trình nâng cấp Greater Underwater Propulsion Power (GUPPY) của Hải quân Mỹ cho các tàu ngầm lớp Gato, Balao và Tench.

Tàu ngầm Nautilus được đặt lườn tại nhà máy đóng tàu của General Dynamics tại Groton, Connecticut, bởi Harry S. Truman vào ngày 14/6/1952.[10] Nó được đặt tên và hạ thủy ngày 21/1/1954, và được hạ thủy tại sông Thames (Conecticut), dưới sự bảo hộ của Mamie Eisenhower-phu nhân Tổng thống Mỹ Dwight D. Eisenhower. Nautilus được đưa vào biên chế vào ngày 30/9/1954, thuyền trưởng là Eugene P. Wilkinson.[9]

Nautilus sử dụng năng lượng lấy từ lò phản ứng nhiệt hạch (Submarine Thermal Reactor (STR), sau này còn gọi là S2W reactor), áp lực nước được chế tạo riêng cho Hải quân Mỹ bởi Westinghouse Electric Corporation. Bettis Atomic Power Laboratory, một phòng thí nghiệm của Westinghouse đảm nhận phát triển thiết kế lò phản ứng cơ bản sử dụng trên tàu Nautilus.[11] Tàu ngầm năng lượng hạt nhân có lợi thế hơn so với tàu ngầm thông thường bởi vì nó không cần không khí, không phát thải, do vậy tàu ngầm năng lượng hạt nhân ở dưới nước trong thời gian dài mà không cần nổi lên như tàu ngầm diesel điện. Thiết kế này là cơ sở cho gần như tất cả các tàu ngầm và tàu nổi chạy bằng năng lượng hạt nhân của Hải quân Mỹ, và cũng được triển khai trên tàu ngầm của các nước khác. Phiên bản thử nghiệm của lò phản ứng (cho tàu ngầm Nautilus) được chế tạo và thử nghiệm tại Phòng thí nghiệm Quốc gia Argonne, Idaho vào năm 1953.[12][13]